// FRAOZO - 3b
// Contains the definition of the dictionary class

#include <iostream>
#include <vector>

class dictionary
{
  public:
   dictionary();
   void readInputFile(const string &fileName);
   void printDict() const;
   int getSize() const;
   string idxString(int idx) const;
   void quickSort(int left, int right);
   void selectionSort();
   bool binarySearch(int &match, int first, int last, 
		     const string &target) const;

  private:
   vector<string> words;
   int partition(int left, int right);
   bool hasPartialMatch(const string &midValue, 
			const string &target) const;
   void swap (string &s1, string &s2);

};

dictionary::dictionary()
:words()
{}

void dictionary::swap(string &s1, string &s2)
{
   string temp=s1;
   s1=s2;
   s2=temp;
}
   

bool dictionary::binarySearch(int &match, 
			      int first, int last, 
			      const string &target) const
//Three cases:
// 1 - No match is found in the dictionary.  match is unchanged, returns false
// 2 - Partial matches are found.  match is unchanged, returns true
// 3 - Exact match is found.  match becomes index of match, returns true
{
   int mid;
   string midValue;
   bool foundMatch=false;
   while (first<last)
   {
      mid = (first+last)/2;
      midValue = words[mid];
      if (midValue == target)
      {
	 //Case 3: found exact match to target
	 foundMatch=true;
	 match=mid;
	 return foundMatch;
      }
      else 
      {
	 if (hasPartialMatch(midValue,target))
	    //Case 2: found a partial match
	    foundMatch=true;
	 if (target<midValue)
	    last = mid;
	 else 
	    first = mid+1;
      }
   }
   return foundMatch;
} // end binarySearch

bool dictionary::hasPartialMatch(const string &midValue, 
				 const string &target) const
//Returns true if target is contained in midValue
//Assume midValue is a larger string then target
{
   int targetSize = target.size();
   string substring = midValue.substr(0, targetSize);
   return (substring == target);
}

void dictionary::quickSort(int left, int right)
//As given in lecture, except operating on private vector data member
{
   int s;
   if (left<right)
   {
      s = partition(left, right);
      quickSort(left, s-1);
      quickSort(s+1, right);
   }
}

int dictionary::partition(int left, int right)
//Privately called by quickSort. 
//Partition the vector around a pivot
{
   string p=words[left];
   int i=left;
   int j=right+1;
   do
   {
      do
	 i=i+1;
      while (words[i]<p && i<right);
      do
	 j=j-1;
      while (words[j]>p);
      swap(words[i], words[j]);
   } 
   while (i<j);
   swap(words[i], words[j]);
   swap(words[left], words[j]);
   return j;
} // end partition


void dictionary::readInputFile(const string &fileName)
//Opens fileName if possible and pushes each string into the 
// words vector
{
   ifstream inputFile;

   string currentWord;

   inputFile.open(fileName.c_str());
   if (!inputFile)
      throw (baseException ("Can't open dictionary file"));
 
   while (inputFile >> currentWord)
      words.push_back(currentWord);

   inputFile.close();
    
}

void dictionary::printDict() const
//Print the contents of the dictionary, one word per line
{
   for (int i=0; i<words.size(); i++)
      std::cout << words[i] << std::endl;
}

int dictionary::getSize() const
{
   return words.size();
}

string dictionary::idxString (int idx) const
{
   return words.at(idx);
}

void dictionary::selectionSort()
//Not used - takes way too long
{
   //foreach element in words
   for (int i=0; i<words.size(); i++)
   {
      //Make smallest an impossibly "large" string
      string smallest("zzzzzzz");
      int smallestIdx;

      //foreach word in the unordered segment
      for (int unIdx=i+1; unIdx<words.size(); unIdx++)
	 if (words[unIdx] < smallest)
	 {
	    smallestIdx = unIdx;
	    smallest = words[smallestIdx];
	 }

      //Swap the current word with the smallest word
      //in the unordered segment
      swap (words[smallestIdx], words[i]);
   }

} // end selectionSort
